/*
 * @lc app=leetcode.cn id=959 lang=javascript
 *
 * [959] 由斜杠划分区域
 */

// @lc code=start
/**
 * @param {string[]} grid
 * @return {number}
 */
var regionsBySlashes = function (grid) {
  const size = grid.length;
  const uf = new UnionFind(4 * size * size);

  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      const idx = i * size + j;
      if (i < size - 1) {
        const bottom = idx + size;
        uf.union(idx * 4 + 2, bottom * 4);
      }
      if (j < size - 1) {
        const right = idx + 1;
        uf.union(idx * 4 + 1, right * 4 + 3);
      }
      if (grid[i][j] === '/') {
        uf.union(idx * 4, idx * 4 + 3);
        uf.union(idx * 4 + 1, idx * 4 + 2);
      } else if (grid[i][j] == '\\') {
        uf.union(idx * 4, idx * 4 + 1);
        uf.union(idx * 4 + 2, idx * 4 + 3);
      } else {
        uf.union(idx * 4, idx * 4 + 1);
        uf.union(idx * 4 + 1, idx * 4 + 2);
        uf.union(idx * 4 + 2, idx * 4 + 3);
      }
    }
  }

  return uf.count;
};

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, i) => i);
    this.count = n;
  }
  find(x) {
    if (x !== this.parent[x]) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    const [ux, uy] = [this.find(x), this.find(y)];
    if (ux ^ uy) {
      this.parent[ux] = uy;
      this.count--;
    }
  }
}
// @lc code=end
